/*
 ============================================================================
 Name        : InsertionSort.c
 Author      : Joshua
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;

void inertionSort(int A[], int len) {
	int i, j;

	for (i = 1; i < len; i++) {
		int tmp = A[i];
		for (j = i; j > 0 && A[j - 1] > tmp; j--) {
			A[j] = A[j - 1];
		}
		A[j] = tmp;
	}
}

void printArr(int A[], int len) {

	int i;
	for (i = 0; i < len; i++) {
		printf("%d,", A[i]);
	}
}

void shellSort(int A[], int len) {
	int i, j, inc;
	for (inc = len / 2; inc > 0; inc /= 2) {
		for (i = inc; i < len; i++) {
			int tmp = A[i];
			for (j = i; j >= inc; j -= inc) {
				if (A[j - inc] > tmp)
					A[j] = A[j - inc];
				else
					break;
			}
			A[j] = tmp;
		}
	}
}

#define LeftChild( i )  ( 2 * ( i ) + 1 )

void PercDown(ElementType A[], int i, int N) {
	int Child;
	ElementType Tmp;

	/* 1*/
	for (Tmp = A[i]; LeftChild( i ) < N; i = Child) {
		/* 2*/Child = LeftChild( i );
		/* 3*/
		if (Child != N - 1 && A[Child + 1] > A[Child])
			/* 4*/Child++;
		/* 5*/if (Tmp < A[Child])
			/* 6*/A[i] = A[Child];
		else
			/* 7*/break;
	}
	/* 8*/A[i] = Tmp;
}
void Swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void Heapsort(ElementType A[], int N) {
	int i;

	/* 1*/
	for (i = N / 2; i >= 0; i--) /* BuildHeap */
		/* 2*/PercDown(A, i, N);
	/* 3*/
	for (i = N - 1; i > 0; i--) {
		/* 4*/Swap(&A[0], &A[i]); /* DeleteMax */
		/* 5*/PercDown(A, 0, i);
	}
}

void myqsort(int A[], int left, int right) {
	int i, last;
	if (left >= right)
		return;
	last = left;
	for (i = left + 1; i <= right; i++) {
		if (A[i] < A[left])
			Swap(&A[i], &A[++last]);
	}
	Swap(&A[left], &A[last]);
	myqsort(A, left, last);
	myqsort(A, last + 1, right);
}

void myqsort2(int A[], int left, int right) {
	int i, j;
	int pivot;
	if (left >= right)
		return;
	pivot = A[left];
	i = left;
	j = right;
	while (1) {
		while (A[++i] < pivot) {
		}
		while (A[--j] > pivot) {
		}
		if (i < j)
			Swap(&A[i], &A[j]);
		else
			break;
	}
	Swap(&A[left], &A[i - 1]);
	myqsort2(A, left, i - 1);
	myqsort2(A, i, right);

}

int main(void) {
	int arr[] = { 3, 12, 4, 1, 5, 9, 2, 6, 52 };

//inertionSort(arr, 9);

//shellSort(arr, 9);
//Heapsort(arr, 9);

	myqsort2(arr, 0, 8);
	printArr(arr, 9);
	return EXIT_SUCCESS;
}
